package org.example.sword2offer.primary;

/**
 * @author: lynn
 * @Descript: 矩形中的路径
 * @视频解析连接： https://www.bilibili.com/video/BV1mK4y1t7Tt?from=search&seid=17590966497524460314
 *
 * 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
 * 路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。
 * 如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。
 * 例如:
 *      a b c e
 *      s f c s
 *      a d e e
 * 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，
 * 因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子
 *
 * @date: 2021/3/27 18:13
 * @version: 1.0
 */
public class Q63_MatrixHasPath {
    public static void main(String[] args) {
        char[][] array={{'a','b','c','e'},{'s','f','c','s'},{'a','d','e','e'}};

        String str="bccse";

        System.out.println(hasPath(array,array.length,array[0].length,str));

    }
    private static boolean hasPath(char[][] matrix, int rows, int cols, String str){

        boolean[][] visited = new boolean[matrix.length][matrix[0].length];
        for(int i = 0 ; i < rows ; i++){
            for(int j = 0 ; j < cols ; j++){
                //以矩阵中的每个点作为起点尝试走出str对应的路径
                //str ，0，是代表str的首个位置index
                if(hasPathCore(str, 0, matrix,i,j,visited)){
                    return true;
                }
            }
        }
        return false;
    };
    private static boolean hasPathCore(String str,int index,char[][] matrix,
                                       int rows,int cols,boolean[][] vis){

        //越界
        if (rows<0 ||rows >matrix.length-1 || cols<0 ||cols>matrix[0].length-1){
            return false;
        }
        //如果访问过了
        if (vis[rows][cols]) {
            return false;
        }
        //值不相等，返回false
        if (str.charAt(index)!=matrix[rows][cols]){
            return  false;
        }
        if (index==str.length()-1) {
            return true;
        }
        vis[rows][cols]=true;
        //下一个字符
        boolean flag= hasPathCore(str,index+1,matrix,rows-1,cols,vis)
                ||hasPathCore(str,index+1,matrix,rows+1,cols,vis)
                ||hasPathCore(str,index+1,matrix,rows,cols-1,vis)
                ||hasPathCore(str,index+1,matrix,rows,cols+1,vis);
        //回溯
        if (flag){
            vis[rows][cols]=false;
        }
        return flag;
    }
}


